package cn.zhl.leetcode.栈;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @program: demos
 * @description: https://leetcode-cn.com/problems/valid-parentheses/
 * @author: 刘振华
 * @create: 2020-04-08 09:44
 **/
public class _20_有效的括号 {
	/*
	给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
	有效字符串需满足：
	左括号必须用相同类型的右括号闭合。
	左括号必须以正确的顺序闭合。
	注意空字符串可被认为是有效字符串。
	示例 1:
	输入: "()"
	输出: true
	示例 2
	输入: "()[]{}"
	输出: true
	示例 3:
	输入: "(]"
	输出: false
	示例 4:
	输入: "([)]"
	输出: false
	示例 5:
	输入: "{[]}"
	输出: true
	*/
	private static Map<Character, Character> map;

	static {
		map = new HashMap<>();
		map.put('(', ')');
		map.put('[', ']');
		map.put('{', '}');
	}

	public static boolean isValid(String s) {
		Stack<Character> stack = new Stack<>();
		int len = s.length();
		for (int i = 0; i < len; i++) {
			char c = s.charAt(i);
			if (map.containsKey(c)) {
				stack.push(c);
			} else {
				if (stack.empty()) {
					return false;
				}
				Character pop = stack.pop();
				if (map.get(pop) != c) {
					return false;
				}
			}
		}
		return stack.empty();
	}

	public static void main(String[] args) {
		System.out.println(isValid("({})["));
	}
}
